package com.clps.algorithm.chapter14.爬楼梯的最少成本;

/**
 * 一个数组cost的所有的数组都是正数,它的第i个数字表示在一个楼梯的第i级台阶往上爬,
 * 在支付了成本cost[i]之后我们可以从第i级台阶往上爬1级,或者2级,结社台阶至少有两级,
 * 我们可以从0级台阶开始触发,也可以从第1级台阶触发,请计算爬上楼梯的最少成本,例如输入数组[1,100,1,1,100,1]
 * 则爬上该楼梯的最少成本是4,分贝经过下标为0,2,3,5这四个台阶,
 */
public class 爬楼梯的最少成本_01 {

    public int minCostClimbingStairs(int[] cost){
        int len = cost.length;
        int[] dp = new int[len];
        helper(cost,len-1,dp);
        return  Math.min(dp[len-2],dp[len-1]);
    }

    private  void helper(int[] cost,int i,int[] dp){
        if(i<2){
            dp[i] = cost[i];
        }else if(dp[i] == 0){
            helper(cost,i-2,dp);
            helper(cost,i-1,dp);
            dp[i] = Math.min(dp[i-2],dp[i-1])+cost[i];
        }
    }

}
